package Seven_sorts.Leetcode;

/**
 * 排序链表
 */
public class Num148_sortList {
    public ListNode sortList(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        //找到链表的中间节点，拆分
        ListNode mid=middle(head);
        ListNode x=head;
        while (x.next!=mid){
            x=x.next;
        }
        x.next=null;
        //先把左右两个子链表排序
        ListNode l1=sortList(head);
        ListNode l2=sortList(mid);
        //合并两个子链表
        return merge(l1,l2);
    }

    /**
     * 将两个有序的子链表合并为大的有序链表
     * @param l1
     * @param l2
     * @return
     */
    private ListNode merge(ListNode l1, ListNode l2) {
        if (l1==null){
            return l2;
        }
        if (l2==null){
            return l1;
        }
        if (l1.val<=l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        }else {
            l2.next=merge(l1,l2.next);
            return l2;
        }
    }

    /**
     * 找到链表的中间节点
     * @param head
     * @return
     */
    private ListNode middle(ListNode head) {
        ListNode fir=head;
        ListNode sec=head;
        while (fir!=null&&fir.next!=null){
            fir=fir.next.next;
            sec=sec.next;
        }
        return sec;
    }
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

}
